//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"
#include "sagittarius/lexer/dfa.h"
#include "sagittarius/lexer/lDeriv.h"
#include "sagittarius/io/io.h"
//#include <stddef.h>
//#include <malloc.h> 
#include <string.h>
//#include <stdio.h>

#if 0
RE_DerivClass** growDCbuf(RE_DerivClass** d, const uint32 m, const uint32 n) {
    uint32 i;
    if(d) {
        for(i=0; i<n; ++i)
            if(d[i])
                re_destroyDC(d[i]);
    }
    free(d);
    return malloc(n*sizeof(RE_DerivClass*));
}

void lex_makeDFAsingle(lASTNode* e) {
    uint32 nd=0;
    RE_DerivClass** d=NULL;
    lASTNode* re=e;
    
    if(!re->d)
        lex_computeDC(re);
    uint32 n=re->d->n;
    if(n > nd) {
        d = growDCbuf(d, n*2);
        nd = n*2;
    }
    for(i=0; i<d
}
#endif

void dfa_destroyOT(dfa_outTran* ot) {
    //SG_WRITE(1, "dfa_destroyOT\n");
    AN(ot->cs);
    re_destroyCS(ot->cs);
    LX_FREE(ot);
}

void dfa_destroyTLink(dfa_outTranLink* l) {
    if(l->cur)
        dfa_destroyOT(l->cur);
    if(l->next)
        dfa_destroyTLink(l->next);
    LX_FREE(l);
}

/// dfa_createState
dfaState* dfa_createState(lexvec* v) {
    //assume v is a temporary node (as created, for example, by the derivative fun)
    dfaState* s = LX_ALLOC(sizeof(dfaState));
    s->v = v;
    s->tend = s->tbeg = LX_ALLOC(sizeof(dfa_outTranLink));
    s->tbeg->cur = NULL;
    s->tbeg->next = NULL;
    s->dstr = NULL;
    AN(s->tend);
    return s;
}

/// dfa_destroyState
void dfa_destroyState(dfaState* s) {
    destroy_lexvec(s->v);
    dfa_destroyTLink(s->tbeg);
    if(s->dstr)
        LX_FREE_POOL_BUFFER(s->dstr);
    LX_FREE(s);
}

/// dfa_create
dfarep* dfa_create() {
    dfarep* dfa = LX_ALLOC(sizeof(dfarep));
    dfa->n = dfa->cap = 0;
    dfa->s = NULL;
    return dfa;
}

/// dfa_destroy
void dfa_destroy(dfarep* dfa) {
    uint32 i;
    AN(dfa);
    for(i=0; i<dfa->n; ++i)
        dfa_destroyState(dfa->s[i]);
    LX_FREE(dfa->s);
    LX_FREE(dfa);
}

/// dfa_grow
void dfa_grow(dfarep* dfa) {
    if(dfa->cap)
        dfa->cap <<= 2;
    else
        dfa->cap = 4;
	{
		dfaState** tmp = LX_ALLOC(dfa->cap*sizeof(dfaState*));
		if(dfa->s) {
			memcpy(tmp, dfa->s, dfa->n*sizeof(dfaState*));
			LX_FREE(dfa->s);
		}
		dfa->s = tmp;
	}
}

/// dfa_stateExists
uint32 dfa_stateExists(lexvec* v, dfarep* dfa) {
    uint32 i;
    for(i=0; i<dfa->n; ++i) {
        if(lexvec_compEq(v, dfa->s[i]->v))
            return i+1;
    }
    return 0;
}

/// dfa_newTran
dfa_outTran* dfa_newTran(uint32 to, RE_CharSet* cs) {
    //SG_WRITE(1, "dfa_newTran\n");
    dfa_outTran* r = LX_ALLOC(sizeof(dfa_outTran));
    r->cs = re_copyCS(cs);
    r->s = to;
    return r;
}

/// dfa_addTransitions
void dfa_addTransitions(dfarep* dfa, dfaState* from, uint32 to, RE_CharSet* cs) {
    dfaState* s = from;
    AN(s->tend);
    AZ(s->tend->cur);
    s->tend->cur = dfa_newTran(to, cs);
    s->tend->next = LX_ALLOC(sizeof(dfa_outTranLink));
    s->tend->next->cur = NULL;
    s->tend->next->next = NULL;
    s->tend = s->tend->next;
}

/// dfa_mergeTransitions
void dfa_mergeTransitions(dfarep* dfa, dfaState* from, uint32 to, RE_CharSet* cs) {
    //attempts to merge with an existing transition
    dfa_outTranLink* l = from->tbeg;
    uint32 ss;
    /*SG_WRITE(1, "dfa_mergeTransitions: set: ");
    re_writeCS(1, cs);
    SG_WRITE(1, "\n");*/
    while(l) {
        if(l->cur) {
            ss=l->cur->s;
            if(ss == to)
                break;
        }
        l = l->next;
    }
    if(l) {
        RE_CharSet* cstmp = re_CSUnion(l->cur->cs, cs);
        re_destroyCS(l->cur->cs);
        l->cur->cs = cstmp;
        /*SG_WRITE(1, "cstmp: ");
        re_writeCS(1, cstmp);
        SG_WRITE(1, "\n");*/
    } else {
        dfa_addTransitions(dfa, from, to, cs);
    }
    //SG_WRITE(1, "New transitions: \n");
    //lex_dumpTransitions(1, from);
}

/// dfa_pushState
uint32 dfa_pushState(dfaState* s, dfaState* from, dfarep* dfa) {
    AN(s->tend);
    if(dfa->n >= dfa->cap)
        dfa_grow(dfa);
    dfa->s[dfa->n] = s;
    return dfa->n++;
}

/*int dfa_accepting(dfarep* dfa, uint32 ss) {
    dfaState* s = dfa->s[ss];
    if(s->e->nullable)
        return 1;
    else
        return 0;
}*/

int dfa_check_for_conflicts(dfarep* dfa, uint32 ss) {
    dfaState* s = dfa->s[ss];
    int found=0;
    size_t i, lastfound;
    
    for(i=0; i<s->v->n; ++i) {
        if(s->v->e[i]->r->nullable) {
            if(found == 1) {
                SG_WRITE(2, "Conflict detected: ");
                if(s->dstr) {
                    SG_WRITE(2, "the string \"");
                    LX_WRITE_BUF(2, s->dstr);
                    SG_WRITE(2, "\" matches the following patterns:\n");
                } else {
                    SG_WRITE(2, "the empty string matches the following patterns:");
                }
                if(s->v->e[lastfound]->id) {
                    LX_WRITE_BUF(2, s->v->e[lastfound]->id);
                    SG_WRITE(2, "\n");
                } else {
                    //TODO: store the string for the expression & print that instead
                    SG_WRITE(2, "(unnamed)\n");
                }
            }
            if(found > 0) {
                if(s->v->e[i]->id) {
                    LX_WRITE_BUF(2, s->v->e[i]->id);
                    SG_WRITE(2, "\n");
                } else {
                    //TODO: store the string for the expression & print that instead
                    SG_WRITE(2, "(unnamed)\n");
                }
            }
            ++found;
            lastfound = i;
        }
    }
    if(found > 1)
        return 1;
    else
        return 0;
}

/** @brief Extend the DFA by for all branches at this state
 * @details Link all out transitions of @a ss either to existing states
 * or to newly created states. If a new state is created then it will
 * be examined by another call to @a dfa_exp.
 * @param dfa The DFA
 * @param ss The index of the state to explore
 * @return 0 for success, other for error
 */
int dfa_exp(dfarep* dfa, uint32 ss) {
    uint32 i;
    lexvec* v;
    dfaState* s = dfa->s[ss];
    uint32 es; //existing state
    /*SG_WRITE(1, "dfa_exp ss = ");
    sg_writeUInt(1, ss);
    SG_WRITE(1, ", cap = ");
    sg_writeUInt(1, dfa->cap);
    SG_WRITE(1, "\n");*/
    //AN(s->tend);
    
    if(!s->v->d)
        lexvec_computeDC(s->v);
    
    {
        RE_DerivClass* d=s->v->d;
        
        AN(s->tend);
        for(i=0; i<d->n; ++i) {
            /*SG_WRITE(1, "loop, dfa->n = ");
            sg_writeUInt(1, dfa->n);
            SG_WRITE(1, ", s = ");
            sg_writePtr(1, s);
            SG_WRITE(1, "\n");*/
            v = lex_computeDerivativeV(s->v, re_CSsample(d->s[i]));
            //SG_WRITE(1, "Derivative:\n");
            //lexvec_dump(2, v, 0);
            if(lexvec_isNull(v)) {
                destroy_lexvec(v);
                continue;
            }
            es = dfa_stateExists(v, dfa);
            if(!es) {
                es = dfa_pushState(dfa_createState(v), s, dfa);
                //Set the example string used to derive the state
                dfa->s[es]->dstr = sg_lex_pushsym(s->dstr, re_CSsample(d->s[i]));
                if(dfa_check_for_conflicts(dfa, es)) {
                    return 1;
                }
                dfa_mergeTransitions(dfa, s, es, d->s[i]);
                //if(!dfa_accepting(dfa, es))
                //keep going even if it is accepting, as there may be
                //multiple accepting states
                if(dfa_exp(dfa, es)) {
                    return 1;
                }
            } else {
                //merge into outtrans
                destroy_lexvec(v);
                --es;
                dfa_mergeTransitions(dfa, s, es, d->s[i]);
            }
        }
    }
    return 0;
}

dfarep* lex_makeDFAvec(lexvec* v) {
    dfarep* dfa=dfa_create();
    
    //if(!v->d)
        //lexvec_computeDC(v);
    if(!dfa_exp(dfa, dfa_pushState(dfa_createState(v), 0, dfa))) {
        return dfa;
    } else {
        //failure
        dfa_destroy(dfa);
        return NULL;
    }
}

void lex_dumpTransitions(int fd, const dfaState* s) {
    dfa_outTranLink* l=s->tbeg;
    SG_WRITE(fd, "    Transitions: ");
    while(1) {
        if(l->cur) {
            re_writeCS(fd, l->cur->cs);
            SG_WRITE(fd, "->");
            sg_writeUInt(fd, l->cur->s);
        }
        l = l->next;
        if(l) {
            if(l->cur)
                SG_WRITE(fd, ", ");
        } else
            break;
    }
    SG_WRITE(fd, "\n");
}

void lex_dumpDFAState(int fd, const dfaState* s) {
    lexvec_dump(fd, s->v, 4);
    lex_dumpTransitions(fd, s);
    if(s->dstr) {
        SG_WRITE(fd, "    Example string: \"");
        LX_WRITE_BUF(fd, s->dstr);
        SG_WRITE(fd, "\"\n");
    }
}

void lex_dumpDFA(int fd, dfarep* dfa) {
    uint32 i;
    SG_WRITE(fd, "DFA:\n");
    SG_WRITE(fd, "  N States: ");
    sg_writeUInt(fd, dfa->n);
    SG_WRITE(fd, "\n  Cap: ");
    sg_writeUInt(fd, dfa->cap);
    SG_WRITE(fd, "\n");
    for(i=0; i<dfa->n; ++i) {
        SG_WRITE(fd, "  State ");
        sg_writeUInt(fd, i);
        SG_WRITE(fd, ":\n");
        lex_dumpDFAState(fd, dfa->s[i]);
    }
}
